package leetcode.tulun.primAndKruskal;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class A1584 {
    class union{

        public union( int n) {
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            this.n = n;
        }


        int[] parent;
        int n;
        //找祖宗同时路径压缩
       int findParent(int a){
            if( parent[a]!=a) parent[a]=findParent(parent[a]);
            return parent[a];
        }
        //合并
        public boolean un(int x, int y) {
         int rootX=findParent(x);
         int rootY=findParent(y);
         if(rootX==rootY)return false;
         parent[rootX]=rootY;
         return true;
        }
        //
        public boolean isConnected(int x, int y){
           return findParent(x)==findParent(y);
        }
    }
    class edge{
        int start;
        int end;
        int length;

        public edge(int x, int y, int[][] points) {
            this.start=x;
            this.end=y;
           this.length=Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public int getLength() {
            return length;
        }

        public void setLength(int length) {
            this.length = length;
        }
    }
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        union union=new union(n);
        //将所有边从小到大排序，直到n-1条边构建出最小生成树
        List<edge> edgeList=new ArrayList<>();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                edgeList.add(new edge(i,j,points));
            }
        }
        //边构建完成，排序
        Collections.sort(edgeList,new Comparator<edge>() {
            @Override
            public int compare(edge o1, edge o2) {
                return o1.length-o2.length;//从小到大排序
            }
        });
        //遍历边
        int num=1;
        int res=0;
        for (edge edge : edgeList) {
            int start = edge.getStart();
            int end = edge.getEnd();
            int length = edge.getLength();
          if(union.un(start,end)){
              //否则
              num++;
              res+=length;
              if(num==n)break;//构建完毕
          }

        }
return res;
    }
}
